package LCS;

public class longestCommonSubstring {
	public int[][] longestCommonSubsequence(String str1, String str2) {
        int[][] matrix = new int[str1.length() + 1][str2.length() + 1];//建立二维矩阵  
        // 初始化边界条件  
        for (int i = 0; i <= str1.length(); i++) {
                matrix[i][0] = 0;//每行第一列置零 
        }
        for (int j = 0; j <= str2.length(); j++) {
                matrix[0][j] = 0;//每列第一行置零  
        }
        // 填充矩阵  
        for (int i = 1; i <= str1.length(); i++) {
                for (int j = 1; j <= str2.length(); j++) {
                        if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                                matrix[i][j] = matrix[i - 1][j - 1] + 1;
                        } else {
                                matrix[i][j] = (matrix[i - 1][j] >= matrix[i][j - 1] ? matrix[i - 1][j]  : matrix[i][j - 1]);
                        }
                        printM(str1,str2,matrix);
                }
        }
        return matrix;
    }
	public void printM(String str1, String str2,int re[][]){
		for (int i = 0; i <= str1.length(); i++) {
            for (int j = 0; j <= str2.length(); j++) {
                    System.out.print(re[i][j] + "   ");
            }
            System.out.println();
	    }
	    System.out.println();
	    System.out.println();
	}
}